209. 长度最小的子数组 | Mkdir700的算法笔记

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

进阶：

如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum

思路及分析

『滑动窗口』的题一般来说，可以把思路给想明白，就是直接操作起来的时候不知道该怎么写

滑动窗口首先就是将窗口的左边界与右边界初始化为0

然后，我们将右边界向右移动，看一下是否能够满足题目的要求

在这道题中的要求就是： 窗口内元素的和>=s

s = 7, nums = [2,3,1,2,4,3]

当窗口包含元素[2, 3, 1, 2]时，大于s，这个时候已经满足了条件

当满足条件时，我们需要做以下几件事

记录当前的结果，在此题中是记录长度
考虑将左边界收缩

以上就是完成一次滑动的过程。

当条件一直不被满足时，一直移动右边界
当条件一致被满足时，一致收缩左边界

完整代码

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        length = len(nums)
        if length == 0:
            return 0
        # 左右边界
        left, right = 0, 0
        ans = float('inf')
        # 当前数组长度
        cur_len = 0
        # 数组和
        total = 0
        while right < length:
            total += nums[right]
            cur_len += 1
            while total >= s:
                ans = min(ans, cur_len)
                total -= nums[left]
                left += 1
                cur_len -= 1
            right += 1
        return ans if ans != float('inf') else 0